package 题目集.动态规划.背包问题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏 现在你一共有X元的预算，平台上所有的 n 个游戏均有折扣 标号为 i
 * 的游戏的原价a_i元，现价只要b_i元 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为w_i
 * 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算 只要满足 : 获得的总优惠金额>=超过预算的总金额 那在心理上就不会觉得吃亏
 * 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。 测试链接 : https://leetcode.cn/problems/tJau2o/
 * 最终快乐值为：w1+w2+..wk 花费=a-b-b。(a-b是优惠的金额)
 *
 * 这一题不能直接用裸的dp，因为价钱的范围太大了。
 */
public class ch02_夏季特惠 {
	static int[] a;
	static 	int[] b;
	static long[] c;
	public static long fun(int i, int sum) {
		if (i < 0)
			return 0;
		if(dp[i][sum]!=-1) {
			return dp[i][sum];
		}
		long noChose = fun(i - 1, sum);
		long chose = 0;
		int rest = sum + a[i] - 2 * b[i];
		if (rest >= 0) {
			chose = (long) (fun(i - 1, rest) + c[i]);
		}
		dp[i][sum]=Math.max(chose, noChose);
		return dp[i][sum];
	}
	static int n,sum;
	static int maxN=500;
	static int maxV=10010+maxN*500;
	static long[][] dp=new long[maxN][maxV];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		sum=sc.nextInt();
		a=new int[n];
		b=new int[n];
		c=new long[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			b[i]=sc.nextInt();
			c[i]=sc.nextLong();
		}
		for(long[] d:dp) {
			Arrays.fill(d, -1);
		}
		long res=fun(n-1,sum);
		System.out.println(res);
	}
}
